﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lesson1
{
    class EdgeTable
    {
        public double ymax;
        public double x;
        public double detx;
        public EdgeTable next;
    }
    class ScanlineFillHelper
    {
        public static void Fill(IntPtr hDC, List<Point> ps, int fillcolor)
        {
            //计算最大值最小值
            int minY = ps.Min(o => o.Y);
            int maxY = ps.Max(o => o.Y);


            EdgeTable[] YXTable = new EdgeTable[maxY - minY + 1];
            for (int i = 0; i < maxY - minY + 1; i++)
            {
                YXTable[i] = new EdgeTable();
            }
            EdgeTable ActiveTable = new EdgeTable();
            //建立有序边
            int count = ps.Count;
            for (int i = 0; i < count; i++)
            {
                Point s = ps[i%count];
                Point e = ps[(i + 1 )% count];
                int cminy = Math.Min(s.Y, e.Y);
                EdgeTable currT = new EdgeTable() { ymax = Math.Max(s.Y, e.Y), x = s.Y > e.Y ? e.X : s.X, detx = (float)(s.X - e.X) / (float)(s.Y - e.Y), next=null };
                EdgeTable tmp = YXTable[cminy - minY].next;
                YXTable[cminy - minY].next = currT;
                currT.next = tmp;
            }
            //建立活化边
            for (int i = minY; i < maxY; i++)
            {

                //从上次活化边更新
                EdgeTable currentET = ActiveTable;
                while (currentET.next!=null)
                {
                    if (i >= currentET.next.ymax) currentET.next = currentET.next.next;
                    else
                    { 
                        currentET = currentET.next;
                        currentET.x += currentET.detx;

                    }
                }
                //从有序边更新活化边
                if (YXTable[i - minY].next != null)
                {
                    currentET = ActiveTable;
                    while (currentET.next != null) currentET = currentET.next;
                    currentET.next = YXTable[i - minY].next;

                }

                //排序
                ActiveTable = Resort(ActiveTable);
                //生成交点奇偶配对进行填充
                currentET = ActiveTable;
                for (EdgeTable ct = ActiveTable.next; ct != null && ct.next != null; ct = ct.next.next)
                {
                    //
                    if (ct.x == ct.next.x&&(ct.ymax - i) * (ct.next.ymax - i) < 0) 
                        ct = ct.next;
                    for (int j = (int)(ct.x + 0.5); j < ct.next.x; j++)
                    {
                        MyGDIClass.SetPixel(hDC, j, i, fillcolor);
                    }
                }

            }

        }

        public static EdgeTable Resort(EdgeTable head)
        {
            if (head == null || head.next == null) return head;
            EdgeTable dummy = new EdgeTable(); // 创建一个哑节点作为排序链表的起始点  
            EdgeTable curr = head;
            while (curr != null) // 遍历原始链表，将每一个节点插入到排序链表的适当位置  
            {
                EdgeTable next = curr.next; // 保存下一个节点，因为我们将删除当前节点  
                EdgeTable prev = dummy; // 从排序链表的起始点开始查找插入位置  
                while (prev.next != null && prev.next.x < curr.x) // 找到插入位置的前一个节点  
                {
                    prev = prev.next;
                }
                curr.next = prev.next; // 将当前节点插入到排序链表中，注意不要忘记删除原来的链接关系  
                prev.next = curr;
                curr = next; // 移动到下一个节点，继续插入过程  
            }
            return dummy.next; // 返回排序链表的起始点，也就是哑节点的下一个节点  
        }
    }
}
